package easy;

/**
 * @author lzy
 * @version v1.0
 * Create DateTime: 2019/2/27 9:51
 */


public class MergeTwoSortedList {
    public static void main(String[] args) {
        ListNode l1 = new MergeTwoSortedList().new ListNode(5);
        l1.next = new MergeTwoSortedList().new ListNode(6);
        l1.next.next = new MergeTwoSortedList().new ListNode(7);

        ListNode l2 = new MergeTwoSortedList().new ListNode(1);
        l2.next = new MergeTwoSortedList().new ListNode(3);
        l2.next.next = new MergeTwoSortedList().new ListNode(4);

        Solution solution = new MergeTwoSortedList().new Solution();
        ListNode merged = solution.mergeTwoLists(l1, l2);

        StringBuilder builder = new StringBuilder();
        while (merged != null) {
            builder.append(merged.val).append("-");
            merged = merged.next;
        }
        System.out.println(builder.substring(0, builder.length() - 1));
    }

    private class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    private class Solution {
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
            if (l1 == null) {
                return l2;
            }
            if (l2 == null) {
                return l1;
            }

            ListNode head = l1;
            ListNode parent = null; // 前置节点，指向l1的父节点

            // 将l2合并到l1中，每次l1只移动一个节点
            while (l2 != null) {
                if (l2.val <= l1.val) {
                    ListNode node = l2.next;
                    l2.next = l1;
                    if (parent == null) {
                        //注意，在开头插入节点要更新head
                        head = l2;
                        l1 = head;
                    } else {
                        parent.next = l2;
                        parent = parent.next;

                    }
                    l2 = node;
                } else {
                    if (l1.next != null) {
                        parent = l1;
                        l1 = l1.next;
                    } else {
                        l1.next = l2;
                        return head;
                    }
                }
            }

            return head;
        }
    }

    private class Solution2 {
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
            ListNode node = new ListNode(0);
            ListNode head = node;
            while (l1 != null && l2 != null) {
                if (l1.val > l2.val) {
                    node.next = new ListNode(l2.val);
                    node = node.next;
                    l2 = l2.next;
                } else if (l1.val < l2.val) {
                    node.next = new ListNode(l1.val);
                    node = node.next;
                    l1 = l1.next;
                } else {
                    node.next = new ListNode(l1.val);
                    node = node.next;
                    node.next = new ListNode(l1.val);
                    node = node.next;
                    l1 = l1.next;
                    l2 = l2.next;
                }
            }

            if (l1 != null) {
                node.next = l1;
            }

            if (l2 != null) {
                node.next = l2;
            }

            return head.next;
        }
    }
}